/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 17655
 * Date: 2025-05-21
 * Time: 15:37
 */
public class test3 {
    int[] tmp;

    public int[] sortArray(int[] nums) {
        tmp = new int[nums.length];
        mergeSort(nums,0,nums.length-1);
        return nums;
    }

    private void mergeSort(int[] nums, int l, int r) {
        if(l>=r){
            return;
        }
        int mid = l+(r-l)/2;
        mergeSort(nums,l,mid);
        mergeSort(nums,mid+1,r);

        // 合并数组
        tmp = new int[r-l+1];
        int cur1 = l;
        int cur2 = r;
        int i=0;
        while(cur1<=mid && cur2<=r){
            tmp[i++] = nums[cur1]<=nums[cur2]?nums[cur1++]:nums[cur2++];
        }
        // 处理未遍历完的
        while(cur1<=mid){
            tmp[i++] = nums[cur1++];
        }
        while(cur2<=r){
            tmp[i++] = nums[cur2++];
        }

        for(int j = l;j<=r;j++){
            nums[j] = tmp[j-l];
        }
    }


}
